Giám mục Tân cử Kiều Công Tùng sinh ngày 24 tháng 8 năm 1964, tại Thủ Đức[gc 1], thuộc Giáo xứ Cao Thái, Tổng giáo phận Sài Gòn.[3] Nguyên quán của ông thuộc giáo xứ Cao Mộc, xã Đồng Tiến, huyện Quỳnh Phụ, tỉnh Thái Bình, thuộc Giáo phận Thái Bình.[9][gc 2] Song thân ông chỉ có hai người con trai và giám mục Tùng là con út trong gia đình,[10] trong một dòng họ có nhiều tu sĩ: một người bác là linh mục Gioakim Đỗ Duy Thản (bên họ mẹ) và một bác là nữ tu (bên họ cha).[11][12] Anh ông là Phêrô Kiều Minh Thanh, từng theo học tại Tiểu chủng viện Á Thánh Phụng Long Xuyên khóa 1971,[11] sau đó lập gia đình và hiện sinh sống tại Hoa Kỳ.[10] Thân phụ ông qua đời khi ông được 9 tháng tuổi,[10] trong khi thân mẫu ông hiện đã 84 tuổi.[11]

Giai đoạn năm 1975, cậu bé Tùng sắp sửa thi vào Tiểu chủng viện Xuân Lộc. Vì thời cuộc, cậu bé Tùng không theo học chủng viện, và ý định đi tu một lần nữa trở lại vào độ tuổi Đại học, khi cậu đủ tuổi để ghi danh vào Đại chủng viện. Do ngại ngần và khó mở lời, chính "cha bác" là linh mục Gioakim Đỗ Duy Thản[12] đã giúp cậu ngỏ lời với mẹ và giúp ghi danh vào Đại chủng viện Thánh Giuse Sài Gòn.[11] Kiều Công Tùng tốt nghiệp trường Đại học Nông Lâm Thành phố Hồ Chí Minh với văn bằng Kỹ sư Nông nghiệp.[2]

Khởi đầu việc tu học từ tháng 10 năm 1993 bằng việc gia nhập Đại chủng viện Thánh Giuse Sài Gòn, chủng sinh Phêrô Kiều Công Tùng tu học tại đây cho đến tháng 7 năm 1999.[3][13] Ông là chủng sinh khóa III của chủng viện này, cùng tu học với ba chủng sinh khác về sau trở thành giám mục là Louis Nguyễn Anh Tuấn, Giuse Đỗ Quang Khang và Giuse Bùi Công Trác. Đây là một việc rất đặc biệt khi có đến bốn giám mục xuất thân từ cùng một khóa Đại chủng viện.[14][15]